/*
 * Project: Sudoku Explainer
 * Copyright (C) 2006-2007 Nicolas Juillerat
 * 
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.rules.fish;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import com.onegravity.sudoku.solver.HintResource;
import com.onegravity.sudoku.solver.R;
import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.IndirectHint;
import com.onegravity.sudoku.solver.core.IndirectHintProducer;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Column;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.data.NeighborManager;
import com.onegravity.sudoku.solver.data.Region;
import com.onegravity.sudoku.solver.data.Row;
import com.onegravity.sudoku.solver.util.BitSetIterator;
import com.onegravity.sudoku.solver.util.CommonTuples;
import com.onegravity.sudoku.solver.util.BitSetFactory;
import com.onegravity.sudoku.solver.util.Permutations;

/**
 * Implementation of X-Wing, Swordfish and Jellyfish solving techniques.
 * The following techniques are implemented depending on the given degree:
 * <ul>
 * <li>Degree 2: X-Wing
 * <li>Degree 3: Swordfish
 * <li>Degree 4: Jellyfish
 * </ul>
 */
public class FishProducer implements IndirectHintProducer {
	
	private final int degree;
	private final boolean look4FinnedFish;

	private static final BitSet emptyBitSet = new BitSet();
	
    public FishProducer(int degree, boolean look4FinnedFish) {
        this.degree = degree;
        this.look4FinnedFish = look4FinnedFish;
    }

    @Override
    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
        getHints(grid, Column.class, Row.class, accu);
        getHints(grid, Row.class, Column.class, accu);
    }

    private <S extends Region,T extends Region> void getHints(Grid grid,
            Class<S> baseType, Class<T> coverType,
            HintsAccumulator accu) throws StopHintProductionException, InterruptedException {

        Permutations perm = new Permutations(degree, 9);
        BitSet[] coverIndices = new BitSet[degree];
        BitSetIterator<Integer> it = null;
        
        // Get occurance count for each value
        int[] occurancesInGrid = new int[10];
        for (int value = 1; value <= 9; value++) {
            occurancesInGrid[value] = grid.getCountOccurancesOfValue(value);
        }

        Region[] baseRegions = grid.getRegions(baseType);
        Region[] coverRegions = grid.getRegions(coverType);
        // Iterate on lines tuples
        perm.reset();
        while (perm.hasNext()) {
            if (Thread.interrupted()) throw new InterruptedException();
            
            // build indexes from permutations (e.g. int[] {1, 5, 8} and BitSet {0, 1, 0, 0, 0, 1, 0, 0, 1})
            int[] baseIndicesArray = perm.nextBitNums();
            BitSet baseIndices = new BitSet(9);
            for (int i = 0; i < baseIndicesArray.length; i++) {
                baseIndices.set(baseIndicesArray[i]);
            }

            // iterate on values
            for (int value = 1; value <= 9; value++) {

                // Pattern is only possible if there are at least (degree * 2) MISSING occurances of the value.
                if (9 - occurancesInGrid[value] >= degree * 2 ) {

                    // Check for exactly the same positions of the value in all lines
                    for (int i = 0; i < degree; i++) {
                    	if (coverIndices[i]==null) coverIndices[i] = new BitSet();
                        baseRegions[baseIndicesArray[i]].getPotentialPositions(coverIndices[i], value);
                    }
                    BitSet unionCoverIndices = CommonTuples.getUnionTuple(coverIndices, degree, true);

                    // (1) simple fish?
                    if (!look4FinnedFish && unionCoverIndices!=null && unionCoverIndices.cardinality()==degree) {
                        IndirectHint hint = createFishHint(baseRegions, coverRegions, baseIndices, unionCoverIndices, value);
                        if (hint!=null && hint.isWorth()) accu.add(hint);
                    }
                    
                    // (2) finned fish?
                    else if (look4FinnedFish && unionCoverIndices!=null) {

                    	// determine if there is a fin
                        for (int i=0; i<degree; i++) {
                        	BitSet finIndices = (BitSet) coverIndices[i].clone();
                            for (int t=0; t<degree; t++) {
                            	if (t!=i) {
                            		BitSet otherOne = coverIndices[t];
                                	finIndices.andNot(otherOne);
                            	}
                            }
                        	int finLength = unionCoverIndices.cardinality()-degree;
                        	if (finIndices.cardinality() == finLength) {
                        		// potential fin discovered
                        		
                        		// collect all fin cells' neighbors
                                Set<int[]> finNeighbors = new HashSet<int[]>();
                                if (it==null) {
                                	it = new BitSetIterator<Integer>(finIndices);
                                }
                                else {
                                	it.restart(finIndices);
                                }
                        		for (; it.hasNext() ;) {
                        			int finIndex = it.next();
                        			Cell finCell = baseRegions[baseIndicesArray[i]].getCell(finIndex);
                                    int[] neighbors = NeighborManager.getNeighbors(grid, finCell.getX(), finCell.getY());
                                    finNeighbors.add(neighbors);
                        		}
                        		
                        		// create hint
                        		boolean isSashimi = isSashimi(coverIndices, unionCoverIndices, finIndices);
                                IndirectHint hint = createFinnedFishHint(baseRegions, coverRegions, baseIndices,
                                					unionCoverIndices, value, finIndices, finNeighbors, isSashimi);
                                if (hint!=null && hint.isWorth()) accu.add(hint);
                        	}
                        }
                    }
                }
            }
        }
    }
    
    private boolean isSashimi(BitSet[] coverIndices, BitSet unionCoverIndices, BitSet finIndices) {
    	// determine if it's a sashimi fish
        for (int i=0; i<degree; i++) {
        	BitSet complementaryIndices = (BitSet) coverIndices[i].clone();
            for (int t=0; t<degree; t++) {
            	if (t!=i) {
            		BitSet otherOne = coverIndices[t];
            		complementaryIndices.andNot(otherOne);
            	}
            }
            if (complementaryIndices.cardinality()==1 && !complementaryIndices.equals(finIndices)) return true;
        }
        return false;
    }

    /**
     * @param baseIndices	indices within baseType e.g. BitSet {0, 1, 0, 0, 0, 1, 0, 0, 1}
     * @param coverIndices	indices within coverType e.g. BitSet {1, 0, 0, 0, 0, 1, 1, 0, 0} 
     */
    private <S extends Region,T extends Region> IndirectHint createFinnedFishHint(
            Region[] baseRegions, Region[] coverRegions, BitSet baseIndices, 
            BitSet coverIndices, int value, BitSet finIndices, Set<int[]> finNeighbors, boolean isSashimi) {

        // Build removable potentials
        Map<Cell,BitSet> cellRemovablePotentials = null;
        BitSet potentialPositions = new BitSet();
        for (int i = 0; i < 9; i++) {
            if (coverIndices.get(i) && !finIndices.get(i)) {
                // check if value appears outside intersection with baseRegion
                //BitSet potentialPositions = coverRegions[i].copyPotentialPositions(value);
                coverRegions[i].getPotentialPositions(potentialPositions, value);
                potentialPositions.andNot(baseIndices);
                if (!potentialPositions.isEmpty()) {
                    for (int j = 0; j < 9; j++) {
                        if (potentialPositions.get(j)) {
                        	Cell cell = coverRegions[i].getCell(j);
                        	// check if the cell is visible from the fin cells
                        	boolean isVisibleOverall = true; 
                        	int pos = cell.getX() + cell.getY()*9;
                        	for (int[] neighbors:finNeighbors) {
                        		boolean isVisible = false;
                        		for (int n:neighbors) {
                        			if (n==pos) {
                        				isVisible = true;
                        				break;
                        			}
                        		}
                        		if (!isVisible) {
                        			isVisibleOverall = false;
                        			break;
                        		}
                            }
                        	if (isVisibleOverall) {
                        		if (cellRemovablePotentials==null) cellRemovablePotentials = new HashMap<Cell,BitSet>();
                        		cellRemovablePotentials.put(cell, BitSetFactory.createOneElement(value));
                        	}
                        }
                    }
                }
            }
        }
        if (cellRemovablePotentials==null || cellRemovablePotentials.isEmpty()) return null;

        // Build highlighted potentials and cells
        List<Cell> cells = new ArrayList<Cell>();
        Map<Cell,BitSet> cellPotentials = new HashMap<Cell,BitSet>();
        Map<Cell,BitSet> finPotentials = new HashMap<Cell,BitSet>();
        for (int base=0; base<9; base++) {
            if (baseIndices.get(base)) {
            	for (int cover = 0; cover < 9; cover++) {
            		if (coverIndices.get(cover)) {
	                	Cell cell = coverRegions[cover].getCell(base);
	                	if (cell.hasPotentialValue(value)) {
	                		cells.add(cell);
	                		if (!finIndices.get(cover)) cellPotentials.put(cell, BitSetFactory.createOneElement(value));
	                		if (finIndices.get(cover)) finPotentials.put(cell, BitSetFactory.createOneElement(value));
	                	}
	                }
                }
            }
        }
        Cell[] allCells = new Cell[cells.size()];
        cells.toArray(allCells);

    	// get region list
        Region[] allRegions = createRegionList(baseRegions, baseIndices, coverRegions, coverIndices, finIndices);

        return new LockingHint(allCells, value, cellPotentials, finPotentials, isSashimi, cellRemovablePotentials, allRegions);
    }

    /**
     * @param baseIndices	indices within baseType e.g. BitSet {0, 1, 0, 0, 0, 1, 0, 0, 1}
     * @param coverIndices	indices within coverType e.g. BitSet {1, 0, 0, 0, 0, 1, 1, 0, 0} 
     */
    private <S extends Region,T extends Region> IndirectHint createFishHint(
            Region[] baseRegions, Region[] coverRegions, BitSet baseIndices, 
            BitSet coverIndices, int value) {

        // Build removable potentials
        Map<Cell,BitSet> cellRemovablePotentials = new HashMap<Cell,BitSet>();
        for (int i = 0; i < 9; i++) {
            if (coverIndices.get(i)) {
                // check if value appears outside intersection with baseRegion
                BitSet potentialPositions = coverRegions[i].copyPotentialPositions(value);
                potentialPositions.andNot(baseIndices);
                if (!potentialPositions.isEmpty()) {
                    for (int j = 0; j < 9; j++) {
                        if (potentialPositions.get(j)) {
                            cellRemovablePotentials.put(coverRegions[i].getCell(j), BitSetFactory.createOneElement(value));
                        }
                    }
                }
            }
        }
        if (cellRemovablePotentials.isEmpty()) return null;
        
        // Build highlighted potentials and cells
        List<Cell> cells = new ArrayList<Cell>();
        Map<Cell,BitSet> cellPotentials = new HashMap<Cell,BitSet>();
        for (int base=0; base<9; base++) {
            if (baseIndices.get(base)) {
            	for (int cover = 0; cover < 9; cover++) {
            		if (coverIndices.get(cover)) {
	                	Cell cell = coverRegions[cover].getCell(base);
	                	if (cell.hasPotentialValue(value)) {
	                		cells.add(cell);
	                		cellPotentials.put(cell, BitSetFactory.createOneElement(value));
	                	}
	                }
                }
            }
        }
        Cell[] allCells = new Cell[cells.size()];
        cells.toArray(allCells);

    	// get region list
        Region[] allRegions = createRegionList(baseRegions, baseIndices, coverRegions, coverIndices, emptyBitSet);
    	
        return new LockingHint(allCells, value, cellPotentials, cellRemovablePotentials, allRegions);
    }
    
    private Region[] createRegionList(Region[] baseRegions, BitSet baseIndices, Region[] coverRegions, BitSet coverIndices, BitSet finIndices) {
        // Build region lists
        List<Region> baseRegionList = new ArrayList<Region>();
        List<Region> coverRegionList = new ArrayList<Region>();
        for (int i = 0; i < 9; i++) {
            if (baseIndices.get(i)) baseRegionList.add(baseRegions[i]);
            if (coverIndices.get(i) && !finIndices.get(i)) coverRegionList.add(coverRegions[i]);
        }
        Region[] allRegions = new Region[baseRegionList.size() + coverRegionList.size()];
        for (int i=0; i<baseRegionList.size(); i++) {
            allRegions[i * 2] = baseRegionList.get(i);
            allRegions[i * 2 + 1] = coverRegionList.get(i);
        }
        return allRegions;
    }
/*    private List<Region> createRegionList(Region[] baseRegions, BitSet baseIndices, Region[] coverRegions, BitSet coverIndices, BitSet finIndices) {
        // Build region lists
        List<Region> result = new ArrayList<Region>();
        for (int i = 0; i < 9; i++) {
            if (baseIndices.get(i)) result.add(baseRegions[i]);
            if (coverIndices.get(i) && !finIndices.get(i)) result.add(coverRegions[i]);
        }
        return result;
    }*/
    
    @Override
	public String getProducerName() {
    	int resId = R.string.producer_xwing;
    	switch (degree) {
    	case 2: resId = look4FinnedFish ? R.string.producer_finned_xwing : R.string.producer_xwing; break;  
    	case 3: resId = look4FinnedFish ? R.string.producer_finned_swordfish : R.string.producer_swordfish; break;  
    	case 4: resId = look4FinnedFish ? R.string.producer_finned_jellyfish : R.string.producer_jellyfish; break;  
    	}
    	return HintResource.getString(resId);
	}
}